package arithmetic.baseAlgorithm.sort;

/**
 * 快速排序
 * 平均时间复杂度 nlog(n)
 *
 * @author zhangyanqi
 * @since 1.0 2017/12/31
 */
public class QuickSort {

    /**
     * 快速排序
     */
    public static int[] sort(int[] toSort, int beginIndex, int endIndex) {
        int pivoteValue = toSort[endIndex];
        int devidePosition = endIndex;
        for (int i = beginIndex; i <= endIndex; i++) {
            if (i == endIndex) {
                int temp = toSort[devidePosition];
                toSort[devidePosition] = toSort[endIndex];
                toSort[endIndex] = temp;
                if (devidePosition - 1 > 1 && devidePosition - 1 > beginIndex) {
                    sort(toSort, beginIndex, devidePosition - 1);
                }
                if (devidePosition + 1 < endIndex && devidePosition + 1 > beginIndex) {
                    sort(toSort, devidePosition + 1, endIndex);
                }
                return toSort;
            }
            if (toSort[i] <= pivoteValue) {
                continue;
            }
            if (toSort[i] > pivoteValue) {
                for (int j = i + 1; j <= endIndex; j++) {
                    if (toSort[j] <= pivoteValue) {
                        int temp = toSort[i];
                        toSort[i] = toSort[j];
                        toSort[j] = temp;
                        devidePosition = j;
                        if (j < endIndex) {
                            i = j;
                        }
                    }
                }
            }
        }
        throw new RuntimeException("finish");
    }

    public static void main(String[] args) {
        int[] ints = {3, 2, 1, 5, 7, 6};
        sort(ints,0,ints.length-1);
        System.out.println(ints[0] + " " + ints[1] + " " + ints[2] + " " + ints[3] + " " + ints[4] + " " + ints[5]);
    }
}
